package commonSort

import (
	"fmt"

	. "../utils"
)

// 冒泡排序的主要思想是：进行交换
func maoPao(arr []int) {
	n := len(arr)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if arr[i] > arr[j] {
				arr[i], arr[j] = SwapInt(arr[i], arr[j])
			}
		}
	}
}

func RunMaoPaoCase() {
	case1 := []int{1, 5, 4, 3, 2}
	maoPao(case1)
	fmt.Println(case1)
}
func RunMergeSortCase() {
	case1 := []int{1, 5, 4, 10, 2, 100, 99, 0, 0, 0, -1}
	case2 := []int{1, 5, 4, 10, 2, 100, 99, 0, 0, 0, -1}
	mergeSort(case1, 0, len(case1)-1)
	fmt.Println(case1)
	quickSort(case2, 0, len(case2)-1)
	fmt.Println(case2)
}

// 归并排序
func mergeSort(arr []int, left, right int) {
	if left < right {
		mid := (right + left) / 2
		mergeSort(arr, left, mid)
		mergeSort(arr, mid+1, right)
		merge(arr, left, mid, right)
	}
}
func merge(arr []int, low, mid, high int) {
	temp := make([]int, high-low+1)
	i, j := low, mid+1
	k := 0
	for i <= mid && j <= high {
		if arr[i] < arr[j] {
			temp[k] = arr[i]
			k++
			i++
		} else {
			temp[k] = arr[j]
			k++
			j++
		}
	}
	for i <= mid {
		temp[k] = arr[i]
		k++
		i++
	}
	for j <= high {
		temp[k] = arr[j]
		k++
		j++
	}
	for k2 := 0; k2 < len(temp); k2++ {
		arr[k2+low] = temp[k2]
	}
}

// 快速排序
func quickSort(arr []int, left, right int) {
	val := arr[left]
	key := left
	i, j := left, right
	for i <= j {
		for j >= key && arr[j] >= val {
			j--
		}
		if j >= key {
			arr[key] = arr[j]
			key = j
		}
		for i <= key && arr[i] <= val {
			i++
		}
		if i < key {
			arr[key] = arr[i]
			key = i
		}
		arr[key] = val
		if key-left > 1 {
			quickSort(arr, left, key-1)
		}
		if right-key > 1 {
			quickSort(arr, key+1, right)
		}
	}
}
